﻿namespace LeetCodeProject._0001_1000._001_100._31_40._034;

public class Solution
{
    public int[] SearchRange(int[] nums, int target)
    {
        if (nums == null || nums.Length == 0)
            return new int[] { -1, -1 };
        var low = 0;
        var high = nums.Length - 1;
        while (low <= high)
        {
            var mid = low + (high - low) / 2;
            if (nums[mid] == target)
            {
                return new int[] { FindFirst(nums, low, mid, target), FindLast(nums, mid, high, target) };
            }

            if (target < nums[mid])
                high = mid - 1;
            else
                low = mid + 1;
        }

        return new int[] { -1, -1 };
    }

    private int FindFirst(int[] arr, int low, int high, int target)
    {
        while (low <= high)
        {
            int mid = low + (high - low) / 2;
            if (arr[mid] == target)
            {
                if (high == low)
                    return mid;
                high = mid;
            }
            else if (target < arr[mid])
            {
                high = mid - 1;
            }
            else
            {
                low = mid + 1;
            }
        }

        return -1;
    }

    private int FindLast(int[] arr, int low, int high, int target)
    {
        while (low <= high)
        {
            int mid = high - (high - low) / 2;
            if (arr[mid] == target)
            {
                if (high == low)
                    return mid;
                low = mid;
            }
            else if (target < arr[mid])
            {
                high = mid - 1;
            }
            else
            {
                low = mid + 1;
            }
        }

        return -1;
    }
}